package Month9;

public class A20250917linklist
{
    public static class SingleLinkedList
    {
        private Node head; // 头节点

        // 节点类
        private static class Node
        {
            char data;    // 数据域
            Node next;    // 指针域

            Node(char data)
            {
                this.data = data;
                this.next = null;
            }
        }

        // 初始化单链表
        public void initList()
        {
            head = new Node('\0'); // 创建头节点，使用空字符作为头节点的数据
        }

        // 插入元素
        public void insert(char element)
        {
            Node newNode = new Node(element);
            Node current = head;
            while (current.next != null)
            {
                current = current.next;
            }
            current.next = newNode;
        }

        // 输出单链表
        public void printList()
        {
            Node current = head.next; // 跳过头节点
            while (current != null)
            {
                System.out.print(current.data + " ");
                current = current.next;
            }
            System.out.println();
        }

        // 获取单链表的长度
        public int length()
        {
            int length = 0;
            Node current = head.next; // 跳过头节点
            while (current != null)
            {
                length++;
                current = current.next;
            }
            return length;
        }

        // 判断单链表是否为空
        public boolean isEmpty()
        {
            return head.next == null;
        }

        // 获取指定位置的元素
        public char get(int index)
        {
            if (index < 0 || index >= length())
            {
                throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + length());
            }
            Node current = head.next; // 跳过头节点
            for (int i = 0; i < index; i++)
            {
                current = current.next;
            }
            return current.data;
        }

        // 查找元素的位置
        public int locate(char element)
        {
            int index = 0;
            Node current = head.next; // 跳过头节点
            while (current != null)
            {
                if (current.data == element)
                {
                    return index;
                }
                current = current.next;
                index++;
            }
            return -1; // 未找到返回-1
        }

        // 在指定位置插入元素
        public void insertAt(int index, char element)
        {
            if (index < 0 || index > length())
            {
                throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + length());
            }
            Node newNode = new Node(element);
            Node current = head;
            for (int i = 0; i < index; i++)
            {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
        }

        // 删除指定位置的元素
        public void deleteAt(int index)
        {
            if (index < 0 || index >= length())
            {
                throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + length());
            }
            Node current = head;
            for (int i = 0; i < index; i++)
            {
                current = current.next;
            }
            current.next = current.next.next;
        }

        // 释放单链表
        public void clear()
        {
            head.next = null;
        }

        public static void main(String[] args)
        {
            SingleLinkedList list = new SingleLinkedList();
            list.initList(); // （1）

            // （2）
            list.insert('a');
            list.insert('b');
            list.insert('c');
            list.insert('d');
            list.insert('e');

            // （3）
            System.out.print("单链表h的内容：");
            list.printList();

            // （4）
            System.out.println("单链表h的长度：" + list.length());

            // （5）
            System.out.println("单链表h是否为空：" + (list.isEmpty() ? "是" : "否"));

            // （6）
            System.out.println("单链表h的第3个元素：" + list.get(2));

            // （7）
            System.out.println("元素a的位置：" + list.locate('a'));

            // （8）
            list.insertAt(3, 'f');
            System.out.print("插入f元素后，单链表h的内容：");
            list.printList();

            // （10）
            list.deleteAt(2);
            System.out.print("删除第3个元素后，单链表h的内容：");
            list.printList();

            // （11）
            list.clear();
            System.out.println("释放单链表h后，单链表h的长度：" + list.length());
        }
    }
}
